package main.面试金典第六版;

import java.util.HashMap;
import java.util.Map;

public class Interview01 {
    public static void main(String[] args) {
        System.out.println("面试题01.01：判定字符是否唯一");
        System.out.println("面试题01.02：判定是否互为字符重排");
        System.out.println("面试题01.03：URL化");
        System.out.println("面试题01.04：回文排列");
        System.out.println("面试题01.05：一次编辑");
        System.out.println("面试题01.06：字符串压缩");
        System.out.println("面试题01.07：旋转矩阵");
        System.out.println("面试题01.08：零矩阵");
        System.out.println("面试题01.09：字符串轮转");
    }
}

class Interview_01_01{
    public boolean isUnique(String astr) {
        if (astr.length()>26) return false;
        int[] counts=new int[26];
        for (int i=0;i<astr.length();i++) {
            if (counts[astr.charAt(i)-'a']==0) counts[astr.charAt(i)-'a']++;
            else return false;
        }
        return true;
    }
}

class Interview_01_02{
    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length()!=s2.length()) return false;
        int[] count1=new int[26],count2=new int[26];
        for (int i=0;i<s1.length();i++) count1[s1.charAt(i)-'a']++;
        for (int j=0;j<s2.length();j++) count2[s2.charAt(j)-'a']++;
        for (int i=0;i<26;i++){
            if (count1[i]!=count2[i]) return false;
        }
        return true;
    }
}

class Interview_01_03{
    public String replaceSpaces(String S, int length) {
        char[] s = S.toCharArray();
        int M = 0;   //有效空格数
        int j = 0;   //供替换时使用
        int N = length;   //有效操作长度
        for (int i = 0; i < N; i++) {//得到原数组有效空格数
            if (s[i] == ' ') M ++;
        }
        M = M * 2 + N;//得到结果数组的有效长度
        char[] arr = new char[M];
        for (int i = 0; i < N; i++) {//进行替换
            if (s[i] == ' '){
                arr[j++] = '%';
                arr[j++] = '2';
                arr[j++] = '0';
            }else arr[j++] = s[i];
        }
        return new String(arr);
    }
}

class Interview_01_04{
    public boolean canPermutePalindrome(String s) {
        int count=0;
        Map<Character,Integer> map=new HashMap<>();
        for (int i=0;i<s.length();i++){
            char temp=s.charAt(i);
            map.put(temp,map.getOrDefault(temp,0)+1);
        }
        for (Character c: map.keySet()){
            if (map.get(c)%2!=0) count++;
        }
        if (count==1||count==0) return true;
        else return false;
    }
}

class Interview_01_05{
    public boolean oneEditAway(String first, String second) {
        if (first.equals(second)) return true;
        int[][] dp=new int[first.length()+1][second.length()+1];
        char[] str1=first.toCharArray(),str2=second.toCharArray();
        for (int i=0;i<dp[0].length;i++) dp[0][i]=i;
        for (int i=0;i<dp.length;i++) dp[i][0]=i;
        for (int i=1;i< dp.length;i++){
            for (int j=1;j<dp[0].length;j++){
                if (str1[i-1]==str2[j-1]) dp[i][j]=dp[i-1][j-1];
                else dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
            }
        }
        return dp[first.length()][second.length()]<2;
    }
}

class Interview_01_06{
    public String compressString(String S) {
        if (S.length() == 0) return S;
        StringBuffer result = new StringBuffer();
        int count = 1;
        char ch = S.charAt(0);
        for (int i = 1; i < S.length(); ++i) {
            if (ch == S.charAt(i)) {
                count++;
            } else {
                result.append(ch);
                result.append(count);
                ch = S.charAt(i);
                count = 1;
            }
        }
        result.append(ch);
        result.append(count);
        return result.length() >= S.length() ? S : result.toString();
    }
}

class Interview_01_07{
    public void process(int[][] matrix,int left,int right){//宏观调度
        int leftUpRow=left,leftUpCol=left,rightUpRow=left,rightUpCol=right,//左上角，右上角
                leftDownRow=right,leftDownCol=left,rightDownRow=right,rightDownCol=right;//左下角，右下角
        for (int i=0;i<right-left;i++){
            int temp1=matrix[leftUpRow][leftUpCol], temp2=matrix[rightUpRow][rightUpCol],
                    temp3=matrix[leftDownRow][leftDownCol],temp4=matrix[rightDownRow][rightDownCol];
            matrix[leftUpRow][leftUpCol]=temp3;
            matrix[rightUpRow][rightUpCol]=temp1;
            matrix[leftDownRow][leftDownCol]=temp4;
            matrix[rightDownRow][rightDownCol]=temp2;
            leftUpCol++;
            rightUpRow++;
            rightDownCol--;
            leftDownRow--;
        }
    }
    public void rotate(int[][] matrix) {
        int right= matrix.length-1,left=0;
        for (int i=0;i< matrix.length/2;i++){
            process(matrix,left,right);
            left++;
            right--;
        }
    }
}

class Interview_01_08{
    public void process(int i,int j,int[][] matrix){
        int row=matrix.length,col=matrix[0].length;
        for (int k=0;k<col;k++) matrix[i][k]=0;//改变行
        for (int k=0;k<row;k++) matrix[k][j]=0;//改变列
    }
    public void setZeroes(int[][] matrix) {
        int row=matrix.length,col=matrix[0].length;
        int[][] temp = new int[row][col];
        for (int i=0;i<row;i++){
            for (int j=0;j<col;j++){
                temp[i][j]=matrix[i][j];
            }
        }
        for (int i=0;i<row;i++){
            for (int j=0;j<col;j++){
                if (temp[i][j]==0) {
                    process(i,j,matrix);
                }
            }
        }
    }
}

class Interview_01_09{
    public boolean isFlipedString(String s1, String s2) {
        if (s1.length()!=s2.length()) return false;
        String doubleS2=s2+s2;
        return doubleS2.contains(s1);
    }
}